1. Field of Invention
The present invention generally relates to a content addressable memory having a function for extending the width of data to be searched to a plurality of words. More particularly, the present invention relates to a content addressable memory having such a mechanism that, if a plurality of words are combined to form one entry, and each of the words constituting the entry is searched to detect a match for all the words, then a match for one entry is detected.
2. Description of Related Art
A content addressable memory (CAM) includes a plurality of memory words arranged (hereinafter referred to as “words”) each having digital data therein. The CAM receives search data, and searches for a memory word containing digital data of the bit pattern matched with the entire portion or a predetermined portion of the bit pattern of the received search data.
FIG. 8 is a circuit block diagram of the fundamental structure of a conventional CAM 100. The CAM 100 includes a great number of words 110_1, 110_2, . . . , and 110—n composed of memory cells of m bits which are arranged side-by-side in the horizontal direction as viewed in FIG. 8 to form one word. The CAM 100 farther includes a search data register 120 which receives and latches the search data of one word. The search data latched by the search data register 120 is supplied to the memory cells that form each word via search bit lines 130_1, 130_2, . . . , and 130—m, where the entire portion or a predetermined portion of the bit pattern of the search data is compared to the bit pattern of the portion corresponding to that bit pattern among the storage data stored in each word to detect a match or mismatch. A match signal of logic ‘1’ is output onto the match line corresponding to the word matched with the bit pattern among match lines 140_1, 140_2, . . . , and 140—n that correspond to the words 110_1, 110_2, . . . , and 110—n, respectively. The remaining match lines have logic ‘0’. As used herein, logic ‘1’ indicates a power supply potential, and logic ‘0’ indicates a ground potential.
The signals output on the match lines 140_1, 140_2, . . . , and 140—n are stored in flag registers 150_1, 150_2, . . . , and 150—n, respectively. As an example shown in FIG. 8, it is assumed that ‘0’, ‘1’, ‘1’, ‘0’, . . . , ‘0’, and ‘0’ are stored in the flag registers 150_1, 150_2, 150_3, 150_4, . . . , 150—n−1, and 150—n, respectively. The signals stored in the flag registers 150_1, 150_2, . . . , and 150—n are input to a priority encoder 160. An encode pulse EP is also input to the priority encoder 160. Each time an encode pulse EP is input, an address signal AD corresponding to a higher priority flag register in the flag registers (the flag registers 150_2 and 150_3 in this example) that store a signal of logic ‘1’ is sequentially output according to a predetermined priority. Herein, the smaller the suffix, the higher the priority. Therefore, when one encode pulse EP is input, the memory address corresponding to the flag register 150_2 is output. The address signal AD output from the priority encoder 160 is then input to an address decoder 170, if necessary. The address decoder 170 decodes the input address signal AD, and outputs an access signal (a signal of logic ‘1’ in this example) onto a word line (the word line 180_2 in this example) corresponding to the input address signal AD among word lines 180_1, 180_2, . . . , and 180—n corresponding to the words 110_1, 110_2, . . . , and 110—n, respectively. The data stored in the word 110_2 corresponding to the word line 180_2 on which the access signal is output is read by an output register 190.
When another encode pulse EP is input, the address of the word 110_3 corresponding to the flag register 150_3 is obtained. Accordingly, the CAM 100 is a memory which searches the storage data which is stored in the words 110_1, 110_2, . . . , and 110—n by using the entire portion or a predetermined portion of the search data to obtain the address of the word containing the storage data matched therewith and to read the entire data which is stored in that word, if necessary.
In the context of a content addressable memory having such a fundamental structure, there has been proposed a technique to extend the width of data to be searched for a match to two or more words. FIG. 9 is a block diagram of an example of the content addressable memory having a data width extension capability, as described in Japanese Patent Application Publication No. Hei 7-226091. The same components as those in the content addressable memory shown in FIG. 8 are designated by the same reference numerals, and a description thereof is not repeated.
The match lines 140_1, 140_2, . . . which extend from the words 110_1, 110_2, . . . are connected to first input terminals of AND gates 200_1, 200_2, . . . , respectively. Second input terminals of the AND gates 200_2, 200_3, . . . are connected to the output terminals of OR gates 210_2, 210_3, . . . , respectively, and first input terminals of the OR gates 210_2, 210_3, . . . are connected to a first search control line 220. However, the OR gate corresponding to the uppermost AND gate 200_1 is omitted in FIG. 9, and a second input terminal of the AND gate 200_1 is directly connected to the first search control line 220.
The output terminals of the AND gates 2001, 2002, . . . are connected to the data input terminals of first flag registers 230_1, 230_2, . . . , respectively. The output terminals of the first flag registers 230_1, 230_2, . . . are connected to the input terminals of second flag registers 240_1, 240_2, . . . , respectively. The output terminals of the second flag registers 240_1, 240_2, . . . are connected to the priority encoder 160 shown in FIG. 8 (not shown in FIG. 9), and are also connected to second input terminals of the OR gates 210_2, 210_3, . . . , respectively, which correspond to the memory words one stage below in FIG. 9.
A match result latch signal S1 which is output on a match result latch control line 250 is input to the clock terminals of each first register and each second flag register. The input data which is input from the data input terminals D of each first and second registers is latched according to the match result latch signal S1. Specifically, the input data is latched by each first flag register at the rise time “a” of the match result latch signal S1, and the input data is latched by each second flag register at the fall time “b” of the match result latch signal S1.
A match search operation for the thus constructed content addressable memory is now described. It is assumed, as shown in FIG. 9, that the storage data A, B, C, D, C, F, . . . are stored in the memory words 110_1, 110_2, 110_3, 110_4, 110_5, 110_6, . . . , respectively. To search the storage data individually rather than in combination, a first search timing signal S2 is output onto the first search control line 220 at the time of inputting search data REF_DATA for the purpose of search operation. Given that data ‘B’ is input as search data REF_DATA, then a match signal of logic ‘1’ is output onto the match line 140_2 corresponding to the word 110_2 which stores the data ‘B’, and is input to the AND gate 200_2. In addition, the first search timing signal S2 is also input to the AND gate 200_2 via the OR gate 210_2. Thus, a signal of logic ‘1 ’ is output from the AND gate 200_2. At this time, a signal of logic ‘0’ is output onto the remaining match lines, and the corresponding AND gates 200_1, 200_3, 200_4, . . . thus output a signal of logic ‘0’.
The signal of logic ‘1’ output from the AND gate 200_2 is latched by the first flag register 230_2 at the rise time “a” of the match result latch signal S1 output on the match result latch control line 250, and is latched by the second flag register 240_2 at the subsequent fall time “b” of the match result latch signal S1.
A signal of logic ‘0’ is latched by the remaining first flag registers 230_1, 230_3, 230_4, . . . at each timing at which the signal of logic ‘1’ is latched by the first flag register 230_2, and is then latched by the remaining second flag registers 240_1, 240_3, 240_4, . . . at each timing at which the signal of logic ‘1’ is latched by the second flag register 240_2. Accordingly, the signals of logic ‘0’, ‘1’, ‘0’, . . . which are latched by the second flag registers 240_1, 240_2, 240_3, . . . are input to the priority encoder 160 shown in FIG. 8, so that the address signal AD of the memory word 110_2 can be obtained.
The search operation for data of the extended width is now described. In this example, the data of two words composed of data ‘B’ and data ‘C’ is searched.
First, data ‘B’ is searched in the same manner as described above. Thus, a signal of logic ‘1’ is latched by the first and second flag registers 230_2 and 240_2 corresponding to the word 110_2. Next, data ‘C’ is input as search data REF_DATA to do a search. At this time, the first search timing signal S2 is not output on the first search control line 220, and the first search control line 220 is maintained in the state of logic ‘0’. When data ‘C’ is input as search data REF_DATA to do a search, a match signal of logic ‘1’ is output onto the match lines 140_3 and 140_5 corresponding to the memory words 110_3 and 110_5, respectively. Since the signal of logic ‘1’ latched by the second flag register 240_2 is input to the OR gate 210_3, the match signal on the match line 140_3 is passed through the AND gate 200_3, and therefore a signal of logic ‘1’ indicating a match is latched by the first and second flag registers 230_3 and 240_3. On the other hand, since the signal of logic ‘0’ latched by the second flag register 240_4 is input to the OR gate 210_5, the match signal on the match line 140_5 is interrupted by the AND gate 200_5, and therefore a signal of logic ‘0’ indicating a mismatch is latched by the first and second flag registers 230_5 and 240_5. In this way, a data match of two words composed of a pair of data ‘B’ and data ‘C’ is detected. A data match of three or more words is detected in the same way.
Although the content addressable memory shown in FIG. 9 has a data width extension capability, the data of extended two words, three words or the like must be stored in adjacent memory words in a predetermined order. That is, if a plurality of data to be searched are stored in memory words which are apart from each other or are reversely ordered, e.g., data ‘B’ is stored after data ‘C’, a data match of a plurality of combined data cannot be detected.
The data structure which requires such a search operation is shown in FIG. 10. FIG. 10 illustrates the data structure in which a data group is composed of sets of four pieces of data which are given attributes I, II, III, and IV, respectively. For clarification of the data group and attribute concept, as an example, the data groups in group numbers 1, 2, 3, 4, and so on include data belonging to an individual, indicating the name in attribute I, the date of birth in attribute II, the address in attribute III, etc.
Suppose that the data groups comprising a plurality of data given attributes I, II, III, and IV are stored in the content addressable memory for the purpose of search operation. For example, if the data group in group No. 1 is searched, in some cases, a user may desire to search for data ‘A’ and data ‘B’ in this order to read the remaining data ‘C’ and ‘D’ in the data group containing a data match, or, for example, may desire to search for data ‘A’ and data ‘D’ to read the remaining data ‘B’ and ‘C’, or to search for data ‘B’ before data ‘A’.
However, the content addressable memory (see FIG. 9) having a data width extension capability cannot perform such a search operation. Furthermore, if data ‘A’ and data ‘B’ are searched for, this content addressable memory cannot distinguish a pair of the data ‘A’ in the column of attribute I and the data ‘B’ in the column of attribute II in the row of group No. 1 from a pair of the data ‘A’ in the column of attribute II and the data ‘B’ in the column of attribute III in the row of group No. 4. For example, even though the information of attributes III and IV of a particular person where a match is found between the “name” information of attribute I and the “date of birth” information of attribute II is desired, noise other than the required information, such as a further match detection between a pair of attributes II and III, might be generated.
The aforementioned content addressable memory further has problems in view of the power consumption. For a search operation for a data group having the data structure shown in FIG. 10, when the data group is searched for a particular attribute, the memory words containing other attributes do not need to be searched, but be searched, as well as the memory word containing the particular attribute. In general, the power consumed by a content addressable memory is largely consumed by the search data lines and match lines. It is therefore important that unnecessary operations for these lines be reduced in order to reduce the power consumption.
For simplification of illustration, in the foregoing content addressable memory, memory words are arranged in a one-dimensional manner. However, a content addressable memory having a large capacity has a two-dimensional structure including a plurality of memory word blocks each being arranged in a one-dimensional manner, and priority encoders in the vertical and horizontal directions in the figure. The content addressable memory having such a two-dimensional structure is well known in the art, and a further illustration or description thereof is omitted herein.
Accordingly, as described above, a conventional content addressable memory having one entry (in which a plurality of memory words are combined in order to form one data group) which is extended to a plurality of words is associated with the following problems:
A match search (AND search) cannot be applied to words of which the addresses are apart from each other in one entry.
The words constituting an entry cannot be searched in an arbitrary order.
A memory word does not have the ability to distinguish data attributes, possibly resulting in an unnecessary search result in some cases.
All the words are always to be searched, thereby significantly increasing the power consumption.